1. Field of the Invention
The present invention relates generally to a network communication performance measuring method and apparatus using a plurality of probing packets (as used herein, xe2x80x9cprobingxe2x80x9d means issuing packets over networks for the purpose of measurement, and the packets used therefor are referred to as xe2x80x9cprobing packetsxe2x80x9d) to estimate available bandwidths of network paths, as well as to a computer readable record medium having a therein stored network communication performance measuring program, and more particularly to a network communication performance measuring method and apparatus ensuring an accurate estimation of path available bandwidths by use of a small number of probing packets, as well as to a computer readable record medium in which is stored the network communication performance measuring program.
2. Description of the Related Arts
In the event of providing high degree of services such as wide area load balancing or quality controls in internets or other communication networks, it is critical to measure available bandwidths of network paths to grasp what level of performances can be provided to users. These available bandwidths may differ to a large extent depending on the processing performances of the communication systems used, the processing abilities of routers lying on the communication paths, the line capacities, and the amount of traffics arising from other users. Conventional network performance measuring methods can include a technique in which the available bandwidths are actually measured through sending and reception of a multiplicity of, e.g., as much as 10,000 probing packets or a technique in which the path performances are estimated by a direct use of delay values of the probing packets.
However, in such a known available bandwidth actual measurement method using a multiplicity of probing packets, any excess load may inevitably act on the networks. The available band estimation method by direct use of delay measurement values of the probing packets may also suffer from a deficiency that the measurement errors are apt to become larger due to strongly affecting disturbances caused by other traffics.
According to the present invention there are provided a method of and an apparatus for measuring a network communication performance, ensuring an accurate estimation of available bandwidths, through sending and reception of a small number of probing packets via a network, without being influenced by any disturbances due to traffics, as well as a computer readable record medium in which is stored a network communication performance measuring program.
The network communication performance measuring method of the present invention comprises:
a sending step in which a sending unit sends a plurality of probing packets at equi-intervals into a network path;
a reception step in which a reception unit receives the plurality of probing packets;
a measurement step in which a measurement unit measures transmission time T(i) from the start of sending of each of the probing packets in the sending step up to the completion of reception of each of the probing packets in the reception step; and
an estimation step in which a performance estimation unit estimates an available bandwidth of the network path from correlations in difference between measurement packet transmission times T(i) measured in the measurement step.
It is to be appreciated that although the reception step and the measurement step follow the sending step, they may be processed at the same time during the sending of the plurality of probing packets in the sending step.
According to such a network communication performance measuring apparatus of the present invention, the network available bandwidth can be estimated by observing the correlations between the transmission times of the plurality of probing packets, whereby it is possible to estimate the available bandwidth, by use of a small number of, e.g., 100 to 200 probing packets, with a high accuracy due to lesser influence arising from other traffics.
The estimation step includes determining a ratio of the time during which the measurement packet transmission time exhibits a random behavior and judging, if the ratio is large and therefore the measurement packet is considered to be less influenced by queuing, that the sending speed of the measurement packet is smaller than the available bandwidth of the path, to thereby estimate the relation of magnitude in available bandwidth between the measurement packet and the path. For example, the estimation step includes finding a ratio giving
(P/xcexcxe2x88x92xcex4+xcex1) less than xcex94T(i) less than xe2x88x92(P/xcexcxe2x88x92xcex4)
where P (bit) is a size of the measurement packet, xcex4 (sec) is a measurement packet sending interval, xcexc (bps) is a bottleneck link speed on a path to be measured, xcex1 is a constant of the order of 0.001 to 0.0000001, and xcex94T(i) is a difference in transmission time between adjacent probing packets, which is defined as ((i+1)th measurement packet transmission time)xe2x88x92(ith measurement packet transmission time); the estimation step including judging, if the ratio is large with the consideration of the probing packets being less influenced by queuing, that the measurement packet sending speed is smaller than the path available bandwidth, to thereby estimate the relation of magnitude in available bandwidth between the measurement packet and the path.
A variant of the network communication performance measuring method of the present invention comprises:
a sending step for sending a plurality of probing packets at equi-intervals into a network path, the plurality of probing packets being designed to reach a predetermined reception site by way of a single or a plurality of predetermined node(s);
a reception step for receiving the plurality of probing packets at the predetermined reception site;
a measurement step for measuring transmission time from the start of sending of each of the probing packets in the sending step up to the completion of reception of each of the probing packets in the reception step; and
an estimation step for estimating a relation of magnitude between a measurement packet sending speed and a path available bandwidth, from correlations between the measurement packet transmission times measured in the measurement step.
In this case as well, the estimation step includes determining a ratio of the time during which the measurement packet transmission time exhibits a random behavior and judging, if the ratio is large and therefore the measurement packet is considered to be less influenced by queuing, that the sending speed of the measurement packet is smaller than the available bandwidth of the path, to thereby estimate the relation of magnitude in available bandwidth between the measurement packet and the path.
Also, the estimation step includes finding a ratio giving
(P/xcexcxe2x88x92xcex4+xcex1) less than xcex94T(i) less than xe2x88x92(P/xcexcxe2x88x92xcex4)
where P (bit) is a size of the measurement packet, xcex4 (sec) is a measurement packet sending interval, xcexc (bps) is a bottleneck link speed on a path to be measured, xcex1 is a constant of the order of 0.001 to 0.0000001, and xcex94T(i) is a difference in transmission time between adjacent probing packets, which is defined as ((i+1)th measurement packet transmission time)xe2x88x92(ith measurement packet transmission time); the estimation step including judging, if the ratio is large with the consideration of the probing packets being less influenced by queuing, that the measurement packet sending speed is smaller than the path available bandwidth, to thereby estimate the relation of magnitude in available bandwidth between the measurement packet and the path.
Another variant of the network communication performance measuring step of the present invention comprises:
a sending step for sending a plurality of probing packets at equi-intervals into a network path;
a reception step for receiving the plurality of probing packets at the same site on a network from which the probing packets are issued in the sending step or at the near site on the network;
a measurement step for measuring transmission time taken for the probing packets to arrive via a path at and return via the path from a specific node within the network determined by the user; and
an estimation step for estimating a relation of magnitude between a measurement packet sending speed and an available bandwidth in reciprocation of the path, from correlations between the measurement packet transmission times measured in the measurement step.
Herein, the estimation step includes finding a ratio giving
(P/xcexcxe2x88x92xcex4+xcex1) less than xcex94T(i) less than xe2x88x92(Pxe2x88x92xcex4)
where P (bit) is a size of the measurement packet, xcex4 (sec) is a measurement packet sending interval, xcexc (bps) is a bottleneck link speed on a path to be measured, xcex1 is a constant of the order of 0.001 to 0.0000001, and xcex94T(i) is a difference in transmission time between adjacent probing packets, which is defined as ((i+1)th measurement packet transmission time)xe2x88x92(ith measurement packet transmission time); the estimation step including judging, if the ratio is large with the consideration of the probing packets being less influenced by queuing, that the measurement packet sending speed is smaller than the path available bandwidth, to thereby estimate the relation of magnitude in available bandwidth between the measurement packet and the path in reciprocation.
In the network communication performance measuring method of the present invention, the sending step, the reception step, the measurement step and the estimation step are iteratively carried out while varying an initialized transfer speed X (bps) by use of any one of bisection method, regula falsi, monotonically increasing method and monotonically decreasing method, to see whether an available bandwidth of a network path exceeds the transfer speed X (bps) to thereby estimate the available bandwidth of the path. Use of the bisection method or of the regula falsi for example ensures a rapid available width measurement of the order of several seconds.
To estimate the one-way available bandwidth of the reciprocative path up to a specific node on the network, the network communication performance measuring method of the present invention further comprises:
a first estimation step for estimating a first available bandwidth of the network path by the execution of the sending step, the reception step, the measurement step and the estimation step;
a second estimation step for estimating a second available bandwidth of the network path by allowing differently sized packets to flow through its sending path and return path by the execution of the sending step, the reception step, the measurement step and the estimation step; and
a third estimation step for estimating a one-way available bandwidth of the network path by judging the state of links within the network path through the comparison of the first and second available bandwidths estimated in the first and second estimation steps.
The third estimation step includes judging whether any half-duplex link exists within the network path and whether the half-duplex link, if any, is bottlenecking therewithin; the third estimation step including, if judgment is made of any one of
a) any half-duplex link exists and is bottlenecking within the path;
b) any half-duplex link exists but is not bottlenecking within the path; and
c) no half-duplex link exists within the path;
estimating a one-way available bandwidth of the half-duplex link.
For example, the third estimation step includes, if a ratio between the first available bandwidth B1 and the second available bandwidth B2 which are estimated with the measurement packet having a size P not less than 4,993 bits is substantially
B1/B2=(P+4,992)/2P
judging that any half-duplex link exists and is bottlenecking within the network, to thereby make a judgment that 2B1 double the first available bandwidth B1 is a one-way available bandwidth of the path. Alternatively, the third estimation step includes, if
B1/B2xe2x89xa0(P+4,992)/2P
judging that any half-duplex link exists but is not bottlenecking within the network path or that no half-duplex link exists within the network path, to thereby make a judgment that the first available bandwidth B1 is a one-way available bandwidth of the path.
The present invention further provides a network communication performance measuring apparatus. The network communication performance measuring apparatus comprises a sending unit for sending a plurality of probing packets at equi-intervals into a network path; a reception unit for receiving the plurality of probing packets sent from the sending unit; a measurement unit for measuring transmission time from the start of sending of each of the probing packets by the sending unit up to the completion of reception of each of the probing packets by the reception unit; and an estimation unit for estimating an available bandwidth of the network path from correlations between measurement packet transmission times measured by the measurement unit.
A variant of the network communication performance measuring apparatus of the present invention comprises a sending unit for sending a plurality of probing packets at equi-intervals into a network path, the plurality of probing packets being designed to reach a predetermined reception site by way of a single or a plurality of predetermined node(s); a reception unit located at the predetermined reception site, for receiving the plurality of probing packets sent from the sending unit; a measurement unit for measuring transmission time from the start of sending of each of the probing packets by the sending unit up to the completion of reception of each of the probing packets by the reception unit; and an estimation unit for estimating a relation of magnitude between a measurement packet sending speed and a path available bandwidth, from correlations between the transmission times of adjacent the probing packets measured by the measurement unit.
Another variant of the network communication performance measuring apparatus of the present invention comprises a sending unit for sending a plurality of probing packets at equi-intervals into a network path; a reception unit located at the same site on a network where the sending unit is located or at the near site on the network, for receiving the plurality of probing packets sent from the sending unit; a measurement unit for measuring transmission time taken for the probing packets to arrive via a path at and then return via the path from a specific node within the network determined by the user; and an estimation unit for estimating a relation of magnitude between a measurement packet sending speed and an available bandwidth in reciprocation of the path, from correlations between the measurement packet transmission times measured by the measurement unit.
Furthermore, the network communication performance measuring apparatus of the present invention executes processings of the sending unit, the reception unit, the measurement unit and the estimation unit while varying an initialized transfer speed X (bps) by use of any one of bisection method, regula falsi, monotonically increasing method and monotonically decreasing method, to see whether an available bandwidth of a network path exceeds the transfer speed X (bps) to thereby estimate the available bandwidth of the path.
The network communication performance measuring apparatus of the present invention further comprises:
a first estimation unit for estimating a first available bandwidth of B1 the network path by the execution of processings of the sending unit, the reception unit, the measurement unit and the estimation unit;
a second estimation unit for estimating a second available bandwidth B2 of the network path by allowing differently sized packets to flow through its sending path and return path by the execution of the sending unit, the reception unit, the measurement unit and the estimation unit; and
a third estimation unit for estimating a one-way available bandwidth of the network path by judging the state of links within the network path through the comparison of the first and second available bandwidths B1 and B2 estimated by the first and second estimation units.
The third estimation unit judges whether any half-duplex link exists within the network path and whether the half-duplex link, if any, is bottlenecking therewithin; the third estimation unit, if judgment is made of any one of
a) any half-duplex link exists and is bottlenecking within the path;
b) any half-duplex link exists but is not bottlenecking within the path; and
c) no half-duplex link exists within the path;
estimating a one-way available bandwidth of the half-duplex link. For example, the third estimation unit, if a ratio between the first available bandwidth B1 and the second available bandwidth B2 which are estimated with the measurement packet having a size P not less than 4,993 bits is substantially
B1/B2=(P+4,992)/2P
judges that any half-duplex link exists and is bottlenecking within the network, to thereby make a judgment that 2B1 double the first available bandwidth B1 is a one-way available bandwidth of the path. Alternatively, the third estimation unit, if
B1/B2xe2x89xa0(P+4,992)/2P
judges that any half-duplex link exists but is not bottlenecking within the network path or that no half-duplex link exists within the network path, to thereby make a judgment that the first available bandwidth B1 is a one-way available bandwidth of the path. The other details of the network communication performance measuring apparatus are basically the same as the case of the method.
The present invention also provides a computer readable record medium having a therein stored network communication performance measuring program. The network communication performance measuring program of the record medium comprises a sending module for sending a plurality of probing packets at equi-intervals into a network path; a reception module for receiving the plurality of probing packets sent from the sending module; a measurement module for measuring transmission time from the start of sending of each of the probing packets by the sending module up to the completion of reception of each of the probing packets by the reception module; and an estimation module for estimating an available bandwidth of the network path from correlations between measurement packet transmission times measured by the measurement module. The other variants and details of the computer readable record medium having the therein stored network communication performance measuring program will be the same as in the cases of the method and apparatus.